Block cipher is a sort of the common key cipher, and is a technique that encrypts a plaintext of a preset block size using a key. Representative of a method for configuring the block cipher is a system that uses Feistel permutation. The Feistel permutation divides a block into two unit blocks A, B, and delivers one A of the unit blocks to a non-linear function with a key. The non-linear function with a key is termed a round function. An output of the round function is Ex-ORed with the other unit block B, and the two unit blocks are then swapped and output. Specifically, (B, B+F(A)) is output in response to the round function F and the inputs (A, B). This processing is repeated a number of times corresponding to a preset number of rounds to generate a ciphertext.
There is also known a method that generalizes the Feistel permutation and that divides a block into two or more unit blocks to apply the Feistel permutation to the unit blocks in terms of two unit blocks as a set. This method is also termed a generalized Feistel network (GFN).
In GFN, each block is divided into a k-number of unit blocks, where k, an even number, is termed the number of division. If the unit block is composed of n-bits, a plaintext is composed of kn bits. If the k-number of unit blocks, obtained on dividing one block, are labeled (m[0], m[1], . . . , m[k−1]), one round of GFN is BlockPerm (m[0], F(m[0])+m[1], m[2], F(m[2])+m[3], . . . , F(m[k−2]), F(m[k−2])+m[k−1]). It is noted that F is a round function and BlockPerm is permutation that interchanges the positions of the k-number of unit blocks.
The BlockPerm that uses cyclic permutation is standard. That is,BlockPerm(v[0],v[1], . . . ,v[k−1])=(v[1],v[2], . . . ,v[k−1],v[0])  [Equation 1] BlockPerm
It is noted that, in List representation, in which output block numbers corresponding to the 0th input block down to the k−1st input block are arrayed, the BlockPerm may be expressed as {1, 2, . . . , k−1, 0}.
An example of GFN that uses cyclic permutation with the number of division k=4 is shown in “CLEFIA” of Non-Patent Document 1. FIG. 10 herein shows the example of GFN that uses cyclic permutation with the number of division k=4.
In the techniques for evaluating structural safety of the block cipher, inclusive of GFN, there are pseudorandomness and strong-pseudorandomness.
In case the target block cipher is GFN with an R-number of rounds, with the number of division k and with the unit block composed of n bits, it is possible with pseudorandomness and strong-pseudorandomness to evaluate whether or not, in case the RK/2-number of the round functions are all regarded to be independent pseudo-random functions, the block cipher in its entirety may become pseudorandom and strong-pseudorandom permutations of kn bits.
The pseudorandom function F is a function that outputs a pseudorandom number F(x), a sequence difficult to distinguish from a true random number in light of the computational volume, from an arbitrary input x. The pseudorandom permutation E is permutation that outputs a pseudorandom number E(x) free of reiterations as ciphertext from an arbitrary plaintext x. The strong-pseudorandom permutation E is permutation that, once E has met the condition for pseudorandom permutation, outputs, even for inverse permutation D of E, a non-duplicate pseudorandom number D(y) as a plaintext from an arbitrary ciphertext y. The strong-pseudorandom permutation means block cipher with the strongest safety that may be currently expected in practice.
It is known from Non-Patent Document 2 that, if BlockPerm is cyclic permutation, for example, the GFN with k+1 rounds becomes pseudorandom permutation and the GFN with 2k rounds becomes strong-pseudorandom permutation. These evaluations provide a necessary minimum number of rounds in constructing practical block cipher. In light of safety and computational volume, such block cipher that satisfies pseudorandomness and strong-pseudorandomness with a smaller number of rounds is desirable. Hence, the number of rounds that satisfies pseudorandomness and strong-pseudorandomness is preferentially used as an index to evaluate the structural desirability or undesirability of the practical block cipher.
The round function, used in the practical block cipher, is generally more vulnerable than the pseudorandom function. Hence, the number of the rounds is selected to be larger than the minimum number of rounds necessary for pseudorandomness to provide for a certain margin for safety. Of course, if the pseudorandomness and strong-pseudorandomness are satisfied with a smaller number of rounds, the number of rounds necessary to secure a certain level of safety margin may be reduced, thus allowing for decreasing the global computational volume.
In a substitution-permutation network configuration (SPN configuration) block cipher, different from the Feistel configuration block cipher, processing termed Mix (S(m[0]), S(m[1]), . . . , S(m[k−1])) is performed as one round. This processing is performed on a kn bit block input (m[0], m[1], . . . , (m[k−1]) using non-linear permutation S with a key. It is noted that if Mix, which linearly transforms kn bits, permutes by interchanging n-bit blocks, different blocks do not affect one another. Hence, MIX is not safe under all situations. It is necessary for Mix to be a permutation including linear block-based operations.
In the 128-bit block cipher SAFER+, disclosed in “SAFER” of Non-Patent Document 3, Mix is implemented by combining 2-block based matrix operations, termed Pseudo-Hadamard Transform PHT, with Armenian shuffle, a permutation by block-based interchange, for k=16 and n=8.    [Non-Patent Document 1] Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, Tetsu Iwata: The 128-Bit Blockcipher CLEFIA. Alex Biryukov (Ed.): Fast Software Encryption, 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, Mar. 26-28, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4593 Springer 2007, pp. 181-195.    [Non-Patent Document 2] Shiho Moriai, Serge Vaudenay: On the Pseudorandomness of Top-Level Schemes of Block Ciphers. Tatsuaki Okamoto (Ed.): Advances in Cryptology—ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, Dec. 3-7, 2000, Proceedings. Lecture Notes in Computer Science 1976 Springer 2000, pp. 289-302.    [Non-Patent Document 3] James L. Massey: On the Optimality of SAFER+ Diffusion, Proceedings of the Second AES Candidate Conference, National Institute of Standards and Technology, 1999. (http://csrc.nist.gov/archive/aes/round1/conf2/papers/massey.pdf)